﻿using System;
using System.Collections.Generic;
using System.Collections;
//using System.Linq;
using System.Text;

namespace AI
{
    public class WayInfo
    {
        public Stack<int> _Path = new Stack<int>();
        public double _Weight = 0;
        public int _EndNodeIndex ;

    }

    public class WayInfoCash
    {

        public int _SNodeIndex;
        public int _ENodeIndex;
        public WayInfo _WayInfo;
        public WayInfo GetCloneWayInfo()
        {

            
            WayInfo wayinfo = new WayInfo();
            int [] array = new int[_WayInfo._Path.Count];
            _WayInfo._Path.CopyTo(array, 0);
            for (int count = _WayInfo._Path.Count - 1; -1 < count; count--)
            {
                wayinfo._Path.Push(array[ count]);
            }

            wayinfo._Weight = _WayInfo._Weight;
            wayinfo._EndNodeIndex = _WayInfo._EndNodeIndex;

            return wayinfo;
        }

    }


    class MyDijkstra
    {
        public MyDijkstra(int NodeCount, int[,] Cost)
        {
            _NodeCount = NodeCount;
            _Distance = new double[_NodeCount];
            _Found = new int[_NodeCount];
            _Via = new int[_NodeCount];
            _Cost = Cost;
            //_Path = new Stack<int>();
            
        }

        List<WayInfoCash> _WayInfoCashList = new List<WayInfoCash>();

        double[] _Distance;
        int[] _Found;
        int[] _Via;
        int[,] _Cost;
        //Stack<int> _Path;
        
        //int _PathCount;

        int _NodeCount;
        //List<uint> _PointList = new List<uint>();

        int GetNextNode()
        {

            int minpos;
            double min = double.MaxValue;

            minpos = -1;

            for (int i = 0; i < _NodeCount; i++)

                if (_Distance[i] < min && _Found[i] == 0)
                {
                    min = _Distance[i];
                    minpos = i;
                }
            return minpos;
        }

        public WayInfo GetPath(int sNodeIndex, int eNodeIndex)
        {

            if (sNodeIndex == eNodeIndex)
            {

                WayInfo wii = new WayInfo();

                wii._Weight = 0;

                wii._EndNodeIndex = eNodeIndex;

                wii._Path.Push(eNodeIndex);
                return wii;
            }

            foreach(WayInfoCash wic in _WayInfoCashList)
            {
                if (wic._SNodeIndex == sNodeIndex && wic._ENodeIndex == eNodeIndex)
                    return wic.GetCloneWayInfo();
            }
            

            //_PointList.Add(sNode._EIndex);

            for (int nodeIndex = 0; nodeIndex < _Distance.Length; nodeIndex++)
            {
                // 이웃거리가 있으면 웨이트값을 없으면 max를 

                _Distance[nodeIndex] = _Cost[sNodeIndex, nodeIndex];

                //if( CurNode._NeighborList.TryGetValue(index,out tempNode))
                //{
                //    _Distance[ index] = tempNode._Weight;
                //}else
                //{
                //    _Distance[ index] = double.MaxValue;
                //}


                _Found[nodeIndex] = 0;
                _Via[nodeIndex] = -1;
                //_Path[index] = -1;
            }

            _Found[sNodeIndex] = 1;


            for (int i = 0; i < _NodeCount - 1; i++)
            {
                int nextIndex = GetNextNode();
                if (nextIndex < 0)
                    break;

                _Found[ nextIndex] = 1;

                //CurNode = CurNode._NeighborList[(uint)nextIndex];

                for (uint j = 0; j < _NodeCount; j++)
                {
                    if (_Found[j] == 0)
                    {
                        // 선택된 경유지를 경유할 경우와 아닌 경우의 비용계산
                        if (_Distance[nextIndex] + _Cost[nextIndex,j] < _Distance[j])
                        {
                            _Distance[j] = _Distance[nextIndex] + _Cost[nextIndex,j];
                            _Via[j] = nextIndex;
                        }
                    }
                }

            }

            WayInfo wi = new WayInfo();


            wi._Weight = _Distance[eNodeIndex];


            wi._EndNodeIndex = eNodeIndex;

            wi._Path.Push(eNodeIndex);

            MakePath(eNodeIndex, wi);

            WayInfoCash newWic = new WayInfoCash();
            newWic._SNodeIndex = sNodeIndex;
            newWic._ENodeIndex = eNodeIndex;
            newWic._WayInfo = wi;
            _WayInfoCashList.Add(newWic);


            return newWic.GetCloneWayInfo();

        }

        void MakePath(int i,WayInfo wi)
        {
            int j;


            j = _Via[i];

            if (j == -1)
                return;

            wi._Path.Push(j);
            if (_Via[j] != -1)
            {

                MakePath(j, wi);
            }

        }

    }
}
